/*
题目: 矩阵查询可获得的最大分数
给你一个大小为 m x n 的整数矩阵 grid 和一个大小为 k 的数组 queries 。

找出一个大小为 k 的数组 answer ，且满足对于每个整数 queres[i] ，你从矩阵 左上角 单元格开始，重复以下过程：

    如果 queries[i] 严格 大于你当前所处位置单元格，如果该单元格是第一次访问，则获得 1 分，并且你可以移动到所有 4 个方向（上、下、左、右）上任一 相邻 单元格。
    否则，你不能获得任何分，并且结束这一过程。

在过程结束后，answer[i] 是你可以获得的最大分数。注意，对于每个查询，你可以访问同一个单元格 多次 。

返回结果数组 answer 。

https://leetcode.cn/problems/maximum-number-of-points-from-grid-queries/description/
 */
public class MaxPoints {
    class Solution {
        int[] ufs = null;
        int[] size = null;
        public int[] maxPoints(int[][] grid, int[] queries) {
            // 并查集
            // 需要抽象成 图 来解决这个问题
            // 由于只需要第一次访问这个点, 就能够获取分数, 所以满足 queries[i] 的就是连通块
            int r = grid.length, c = grid[0].length;
            int k = queries.length;
            ufs = new int[r * c];  // 需要转化成 一维并查集 来使用
            size = new int[r * c];
            for (int i = 0; i < ufs.length; i ++) {
                ufs[i] = i;
                size[i] = 1;
            }


            // 获取所有边的边权, 边权取 两个点权的 最大值
            List<int[]> edges = new ArrayList<> ();  // 记录边权, 和 顶点
            for (int i = 0; i < r; i ++) {
                for (int j = 0; j < c; j ++) {
                    // 由于两个点之间只需要一个边, 所以我们规定两个点的连接只取 上方 和 左方
                    if (i > 0) {
                        edges.add(new int[] {Math.max(grid[i][j], grid[i - 1][j]), i * c + j, (i - 1) * c + j});
                    }
                    if (j > 0) {
                        edges.add(new int[] {Math.max(grid[i][j], grid[i][j - 1]), i * c + j, i * c + j - 1});
                    }
                }
            }

            // 根据边权进行排序, 对于每一个 queries[i], 对应的答案就是左上角(0)的连通图大小
            edges.sort(Comparator.comparingInt(o -> o[0]));
            // 再对 queries 的下标进行排序
            List<int[]> quer = new ArrayList<> ();
            for (int i = 0; i < k; i ++) {
                quer.add(new int[] {i, queries[i]});
            }
            quer.sort(Comparator.comparingInt(o -> o[1]));

            // 双指针计算答案
            int[] src = new int[k];
            int p = 0, q = 0; // 双指针, p 为 src, q 为 queries
            int edgesLen = edges.size();
            while (q < k) {
                // 所有的权值都小于这个点
                int[] curQuer = quer.get(q);
                while (p < edgesLen && edges.get(p)[0] < curQuer[1]) {
                    // 合并两个点
                    unit(edges.get(p)[1], edges.get(p)[2]);
                    p ++;
                }
                if (curQuer[1] > grid[0][0])
                    src[curQuer[0]] = size[find(0)];
                q ++;
            }

            return src;
        }

        // 并查集 —— 路径压缩
        private int find(int x) {
            if (ufs[x] != x) ufs[x] = find(ufs[x]);
            return ufs[x];
        }

        private void unit(int from, int to) {
            int f = find(from), t = find(to);
            if (f == t) return ;

            size[f] += size[t];
            ufs[t] = f;
        }
    }
}
